//题目:
// 给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。
// 你可以 按任意顺序 返回答案。
// 生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 104 。

// 示例 1：
// 输入：expression = "2-1-1"
// 输出：[0,2]
// 解释：
// ((2-1)-1) = 0 
// (2-(1-1)) = 2

// 示例 2：
// 输入：expression = "2*3-4*5"
// 输出：[-34,-14,-10,-10,10]
// 解释：
// (2*(3-(4*5))) = -34 
// ((2*3)-(4*5)) = -14 
// ((2*(3-4))*5) = -10 
// (2*((3-4)*5)) = -10 
// (((2*3)-4)*5) = 10
 
// 提示：
// 1 <= expression.length <= 20
// expression 由数字和算符 '+'、'-' 和 '*' 组成。
// 输入表达式中的所有整数值在范围 [0, 99] 
// 输入表达式中的所有整数都没有前导 '-' 或 '+' 表示符号。
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
//代码
class Solution 
{
public:
    vector<int> diffWaysToCompute(string expression) 
    {
        //预备处理————将expression分割成 "val sep" 的格式，以便后续计算
        vector<pair<int,char>> vv;
        int left=0,right=0;
        expression+="+";
        for(auto e:expression)
        {
            if(e=='+' || e=='-' || e=='*')
            {
                vv.push_back({stoi(expression.substr(left,right-left)),e});
                left=right+1,right=left;
            }
            else
                right++;
        }
        int n=vv.size();
        //1.创建dp表————dp[i][j]表示：
        vector<vector<vector<int>>> dp(n,vector<vector<int>>(n));
        //2.初始化————暂无

        //3.填表————动态转移方程:dp[i][j]=(i,j-1)$(j,j) + (i,j-2)$(j-1,j) + ... + (i,i)$(i+1,j)
        for(int i=n-1;i>=0;i--)
        {
            dp[i][i].push_back(vv[i].first);
            for(int j=i+1;j<n;j++)
            {
                for(int k=j;k>=i+1;k--)
                {
                    func(dp[i][k-1],dp[k][j],vv[k-1].second,dp[i][j]);
                }
            }
        }
        //4.确定返回值
        return dp[0][n-1];
    }
    //func功能：拿到vv1中所有元素 与 vv2中所有元素 进行 sep 运算后的结果
    void func(const vector<int>& vv1,const vector<int>& vv2,char sep,vector<int>& ret)
    {
        for(auto x:vv1)
        {
            for(auto y:vv2)
            {
                if(sep=='+') ret.push_back(x+y);
                if(sep=='-') ret.push_back(x-y);
                if(sep=='*') ret.push_back(x*y);
            }
        }
    }
};